package tree.递归;

import po.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N二叉搜索树中的众数501.java
 * @Description https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/
 * @createTime 2021年05月11日 16:59:00
 */
public class N二叉搜索树中的众数501 {
    int count = 0;
    int max = 1;
    int preValue = 0;
    List<Integer> list = new ArrayList<>();

    /**
     * 使用中序遍历的方式，来进行处理
     */
    public int[] findMode(TreeNode root) {
        if (root == null) {
            return null;
        }
        find(root);
        //初始化数组
        int [] result = new int [list.size()];
        //list转array
        for(int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    private void find(TreeNode node) {
        if (node == null) {
            return;
        }
        find(node.left);
        //当前节点是不是跟前一个相等
        if (node.val == preValue) {
            count++;
        } else {
            preValue = node.val;
            count=1;
        }
        /**
         * 如果当前这个数大 出现的次数和 > 之前记录的最大的数量，
         * 1. 清除集合
         * 2. 添加新的最大次数的值
         * 3. 更新最大出现次数
         */
        if (count > max) {
            list.clear();
            list.add(preValue);
            max=count;
        } else if (count == max) {
            list.add(preValue);
        }
        find(node.right);
    }

}
